//给你一个整数数组 nums ，你需要找出一个 连续子数组 ，如果对这个子数组进行升序排序，那么整个数组都会变为升序排序。
//
// 请你找出符合题意的 最短 子数组，并输出它的长度。
//
//
//
//
//
// 示例 1：
//
//
//输入：nums = [2,6,4,8,10,9,15]
//输出：5
//解释：你只需要对 [6, 4, 8, 10, 9] 进行升序排序，那么整个表都会变为升序排序。
//
//
// 示例 2：
//
//
//输入：nums = [1,2,3,4]
//输出：0
//
//
// 示例 3：
//
//
//输入：nums = [1]
//输出：0
//
//
//
//
// 提示：
//
//
// 1 <= nums.length <= 10⁴
// -10⁵ <= nums[i] <= 10⁵
//
//
//
//
// 进阶：你可以设计一个时间复杂度为 O(n) 的解决方案吗？
//
//
// Related Topics 栈 贪心 数组 双指针 排序 单调栈 👍 894 👎 0

package leetcode.editor.cn;

class 最短无序连续子数组 {
    public static void main(String[] args) {
        Solution solution = new 最短无序连续子数组().new Solution();
        int[] nums = new int[]{2, 6, 4, 8, 10, 9, 15};
        int unsortedSubarray = solution.findUnsortedSubarray(nums);
        System.out.println(unsortedSubarray);
    }

    //leetcode submit region begin(Prohibit modification and deletion)
    class Solution {
        public int findUnsortedSubarray(int[] nums) {
            if (nums == null || nums.length < 2) {
                return 0;
            }
            int n = nums.length;
            //从左往右找最后一个不满足条件的
            int right = -1;
            int max = Integer.MIN_VALUE;
            for (int i = 0; i < n; i++) {
                if (max > nums[i]) {
                    right = i;
                }
                max = Math.max(max, nums[i]);
            }
            //从右往左找最后一个不满足条件的
            int min = Integer.MAX_VALUE;
            int left = n;
            for (int i = n - 1; i >= 0; i--) {
                if (min < nums[i]) {
                    left = i;
                }
                min = Math.min(min, nums[i]);
            }
            return Math.max(0, right - left + 1);
        }
    }
//leetcode submit region end(Prohibit modification and deletion)

}
